class Node:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
curr = self.root
for w in word:
if w not in curr.children:
curr.children[w] = Node()
curr = curr.children[w]
curr.end = True
def search(self, word: str) -> bool:
curr = self.root
for w in word:
if w not in curr.children:
return False
curr = curr.children[w]
return curr.end
def startsWith(self, prefix: str) -> bool:
curr = self.root
for w in prefix:
if w not in curr.children:
return False
curr = curr.children[w]
return True
